#include<bits/stdc++.h>
using namespace std;
typedef struct Lnode{
    int data;
    struct Lnode *next;
}*ls;
typedef struct TNode{
    int val;
    struct TNode *lchild;
    struct TNode *rchild;
}*tree;
#define maxvertexs 10

typedef struct EdgeNode{
    // int weight; //权值
    struct EdgeNode *next;
    int adjvex;//边所指向的节点
}EdgeNode;
typedef struct verNode{
    char data;//顶点信息
    EdgeNode *firstedge;//以该顶点为起始的第一条边
}VNode,adjList[maxvertexs];
typedef struct GraphAdjList{
    adjList vertices;
    int numEdges,numVertexes;
}GraphAdjList;

bool visited[maxvertexs];
queue<int> Q;
//创建邻接表
void Create(GraphAdjList *G){

    int i,j,k;
    printf("输入顶点数和边数:\n");
    scanf("%d%d",&G->numVertexes,&G->numEdges);

    //输入顶点信息
    printf("输入顶点信息:\n");
    for(i=0;i<G->numVertexes;i++){
        getchar();//读取上个缓冲区中的换行，读取%c时需要
        scanf("%c",&G->vertices[i].data);
        G->vertices[i].firstedge=NULL;           //将指向边表的指针初始化 
    } 

    //建立边表
    printf("输入边(Vi,Vj)中的下标i,j:\n"); 
    for(k=0;k<G->numEdges;k++){
        scanf("%d%d",&i,&j);
        EdgeNode *p=(EdgeNode *)malloc(sizeof(EdgeNode));
        p->adjvex=j;                                //存储弧头 
        p->next=G->vertices[i].firstedge;            //头插法插入边结点 
        G->vertices[i].firstedge=p;

        //下面代码有向图无,无向图有 
        p=(EdgeNode *)malloc(sizeof(EdgeNode));
        p->adjvex=i;                                //存储弧头 
        p->next=G->vertices[j].firstedge;            //头插法插入边结点 
        G->vertices[j].firstedge=p;
    }
}
void print_Mg(GraphAdjList mg){
    printf("邻接表为：\n");
    for(int i=0;i<mg.numVertexes;i++){
        EdgeNode *p=mg.vertices[i].firstedge;
        printf("%c",mg.vertices[i].data);
        while(p){
            printf("->%c->",mg.vertices[p->adjvex].data);
            p=p->next;
        }
        printf("\n");
    }
}
/*
给定一颗二叉树，若二叉树的某个结点，其左子树所有节点之和与右子树所有结点之和相等，
则称该节点为平衡节点，编写函数，判断节点值为整数的二叉树是否存在平衡结点。
*/
tree newNode(int val){
    tree node=(tree)malloc(sizeof(struct TNode));
    node->val=val;
    node->lchild=NULL;
    node->rchild=NULL;
    return node;
}
tree create_Tree(tree root,int val){
    if(root==NULL)
        return newNode(val);
    if(root->val>val){
        root->lchild=create_Tree(root->lchild,val);
    }else{
        root->rchild=create_Tree(root->rchild,val);
    }
    return root;
}

void postOrder(tree root){//根左右--->右左根    根右左--->左右根
    if(root==NULL)
        return;
    stack<tree> s;
    s.push(root);
    stack<tree> res;
    while(!s.empty()){
        tree node=s.top();
        res.push(node);
        s.pop();
        if(node->lchild) s.push(node->lchild);
        if(node->rchild) s.push(node->rchild);//后入先出
    }
    while(!res.empty()){
        printf("%d ",res.top()->val);
        res.pop();
    }
}
void levelOrder(tree root){
    if(root==NULL)
        return;
    queue<tree> q;
    q.push(root);
    while(!q.empty()){
        tree node=q.front();
        printf("%d ",node->val);
        q.pop();
        if(node->lchild) q.push(node->lchild);
        if(node->rchild) q.push(node->rchild);
    }
}

bool judge(tree a,tree b){
    if(a==NULL&&b==NULL){
        return true;
    }else if(a==NULL||b==NULL){//只有一个不空
        return false;
    }else if(a->val!=b->val){//都不为空，但是数据不相等
        return false;
    }else{
        return judge(a->lchild,b->rchild)&&judge(a->rchild,b->lchild);
    }
}
bool fun(tree root){
    if(root==NULL)
        return true;
    return judge(root->lchild,root->rchild);
}
void visit(GraphAdjList g,int v){
    printf("%c->",g.vertices[v].data);
}
int FirstNeighbor(GraphAdjList g,int v){
    if(g.vertices[v].firstedge){
        return g.vertices[v].firstedge->adjvex;
    }else{
        return -1;
    }
}
int NextNeighbor(GraphAdjList g,int v,int w){
    EdgeNode *p=g.vertices[v].firstedge;
    while(p->adjvex!=w)//一直找到指向 上一个 被遍历过的顶点节点 的边节点
        p=p->next;
    if(NULL!=p->next)//如果此时 p表示的边节点还 不是最后一个就返回其下一个边节点指向的顶点节点
        return p->next->adjvex;
    else
        return -1;
}
void dfs(GraphAdjList g,int v){
    visit(g,v);
    visited[v]=true;
    for(int w=FirstNeighbor(g,v);w>=0;w=NextNeighbor(g,v,w)){
        if(!visited[w]){
            dfs(g,w);
        }
    }
}
void dfs_traverse(GraphAdjList g){
    for(int v=0;v<g.numVertexes;v++){//对标记数组进行初始化
        visited[v]=false;
    }
    for(int v=0;v<g.numVertexes;v++){//这是考虑非连通的情况
        if(!visited[v])
            dfs(g,v);
    }
    printf("\n");
}

void bfs(GraphAdjList g,int v){
    visit(g,v);
    visited[v]=true;
    Q.push(v);
    while(!Q.empty()){
        v=Q.front();
        Q.pop();
        for(int w=FirstNeighbor(g,v);w>=0;w=NextNeighbor(g,v,w)){
            if(!visited[w]){
                visit(g,w);
                visited[w]=true;
                Q.push(w);
            }
            
        }
    }
}
void bfs_traverse(GraphAdjList g){
    for(int v=0;v<g.numVertexes;v++){
        visited[v]=false;
    }
    for(int v=0;v<g.numVertexes;v++){
        if(!visited[v]){
            bfs(g,v);
        }
    }
}

void v2u(GraphAdjList g,int v,int u,bool &reach){
    visited[v]=true;
    for(int w=FirstNeighbor(g,v);w>=0;w=NextNeighbor(g,v,w)){
        if(w==u){
            reach=true;
            break;
        }
        if(!visited[w])
            v2u(g,w,u,reach);
    }
}
void v2u_fun(GraphAdjList g,int v,int u,bool &reach){
    for(int vi=0;vi<g.numVertexes;vi++){
        visited[vi]=false;
    }
    v2u(g,v,u,reach);
}

ls create_list(ls head){
	if(head == NULL){
		head=(ls)malloc(sizeof(struct Lnode));
		head->next=NULL;
	}
	ls p=head;
	int x;
	scanf("%d",&x);
	while(x!=-1){
		ls node=(ls)malloc(sizeof(struct Lnode));
		node->data=x;
		node->next=p->next;
		p->next=node;
		p=node;//尾插法
		scanf("%d",&x);
	}
	p->next=NULL;//注意
	return head;
}
void printL(ls head){
	ls p=head->next;
	while(p){
		printf("%d->",p->data);
		p=p->next;
	}
}
void del_duplicate_num(ls head){
    ls p=head->next;
    ls pre;
    while(p){
        ls q=p->next;
        pre=p;
        while(q){
            if(p->data==q->data){//删除q
                pre->next=q->next;
                free(q);//删除一定要记得释放内存
                q=pre->next;//q指针指回链表
            }else{
                pre=q;
                q=q->next;
            }
        }
        p=p->next;
    }
}
#define maxsize 10
void f(int a[],int n)
{
	int dp[maxsize];
    int max=a[0],head=0,tail=0;
    for(int i=0;i<n;i++){
        if(i==0){
            dp[i]=a[i];
        }else{
            if(dp[i-1]<0){
                dp[i]=a[i];
                head=i;
            }else{
                dp[i]=dp[i-1]+a[i];
            }
        }
        if(max<dp[i]){
            max=dp[i];
            tail=i;
        }
    }
    printf("a[%d]+...+a[%d] = %d",head,tail,max);
}

int main(){
    // tree root=NULL;
    // int arr[7]={40,30,30,10,10,60,60};
	// for(int i=0;i<7;i++){
	// 	root=create_Tree(root,arr[i]);
	// }
    // printf("\n后序非递归遍历\n");
    // postOrder(root);
    // printf("\n层次遍历\n");
    // levelOrder(root);
    // printf("\n是否对称:");
    // printf("%d",fun(root));

    // GraphAdjList mg;
    // Create(&mg);
    // print_Mg(mg);
    // printf("\ndfs:");
    // dfs_traverse(mg);
    // printf("\nbfs:");
    // bfs_traverse(mg);
    // printf("\nv到u是否可达:");
    // bool reach=false;
    // v2u_fun(mg,0,5,reach);
    // printf("%d",reach);

    // ls head=NULL;
    // head=create_list(head);
    // del_duplicate_num(head);
    // printL(head);
    int a[5]={1,-1,-2,3,5};
    f(a,5);
    return 0;
}